Virtual DOM
App（JS程序）可以通过DOM操作创建或更改DOM元素，DOM元素也可以通过监听并触发事件来影响JS
然而对于对于用js写的每个组件，我们需要自行手动去完成DOM更新和事件处理，效率低下
（e.g. 我用js写了一个复杂的大组件，现在想改其中一个小部分（子组件），我可以：1. 直接覆盖DOM树上整个大组件的节点，不需要引入额外代码，但DOM操作复杂性能低，或2. 通过一系列DOM查找，找到要修改的子组件所在的DOM节点，然后覆盖这个小节点，但是需要手动引入大量额外操作或代码）
React为解决上述问题引入了Virtual Dom：
- js创建组件后通过
React.createElement函数生成虚拟DOM树，然后通过Virtual DOM来创建或更改真实的DOM树 - DOM触发的事件会先冒泡至Virtual DOM，再由Virtual DOM转发到具体的js组件或函数去处理事件
Virtual Dom优势
我们只需建立js组件并维护其状态，Virtual DOM会自动完成DOM更新和事件处理，从而提升开发效率
Virtual DOM通过Diff算法来比较新旧Virtual DOM树，从而得出最高效的DOM更新和操作步骤，因而提升性能
（实际上Virtual DOM最终还是要进行实际的DOM操作，因而不会直接提升DOM操作的性能）
不同平台可以根据Virtual DOM画出对应平台的UI层（e.g. react-native），从而实现了跨平台能力
Virtual DOM节点对象属性
- type：组件类型：原生HTML元素（div, span）/ Function Component / Class Component
- key：组件的唯一标识（用于Diff算法）
- ref：指向原生的DOM节点
- props：传入组件的props（注意children也是props的一个属性，即子组件由此访问）
- owner：父组件的Virtual DOM节点
Virtual DOM事件处理
react所有组件的事件（非原生事件，以下称react事件）都是挂载在document上
直到事件触发后冒泡至document后，react才开始执行react事件
执行顺序：非挂载在document上的原生事件 => react事件 => 挂载在document上的原生事件
（不建议混用react事件和原生事件） ref
Diff算法
归纳三点（如果不想看后续详细介绍）：
- 同级节点（具有相同父节点的子节点）为一组进行比较（tree diff）
- 节点间通过比较节点类型进行快速判断（component diff）
- 使用key对于同组节点进行比较和移动操作，避免重复删除和重建节点（element diff）
Virtual DOM带来的性能提升主要源于React实现的高效Diff算法。Diff算法主要用于计算从一颗树变换到另一个树所需要的最少操作次数（添加/删除/移动节点）。
传统Diff算法平均复杂度为n^3，react引入的改进版Diff算法平均复杂度降至n
用户触发的事件均可能造成DOM树的变动，主要分为以下几种：
- 同一层级（具有相同父节点的兄弟节点）的DOM节点之间的变动：e.g. 新增/插入/删除/随机排序列表项
- 一个DOM节点影响另一个DOM节点（例如redux状态共享，父子节点通过props/callback状态共享）
- DOM节点间的跨层级移动（例如同级的AB节点，A节点移动至B的子节点）（此种情况出现次数极少，忽略不计）
基于上述变动方式，React设计了如下步骤用于计算如何变换DOM树：
tree diff
由于DOM节点间的跨层级移动出现极少，因此可以完全忽略此种情况，比较两颗树时只对同一层次对应的节点进行比较
（如上图：根节点和根节点比较，同一层次具有相同父节点的节点为一组进行比较）
而对于跨层级移动的节点（上图A），则会经历一次节点销毁和节点重建的过程，效率较低。但由于此种情况出现极少，整体而言react diff算法效率还是较高
component diff
上面tree diff进行同级比较时，需要判断两个节点是否相同，如果不同则会被替换或销毁
react判断节点（以及其子节点）是否相同，不会通过递归的方式一一比较子节点，而是直接通过判断两个节点的类型（class，即组件名）是否相同，对于不同的节点进行操作
（react官方的解答是，对于不同类型的组件节点，存在相同DOM树的概率极低，因而不用浪费时间在后续比较）
对于类型相同的节点，则继续递归其子节点进行判断，但是react也允许用户使用
shouldComponentUpdate()来判断是否需要对该节点进行后续diff运算，从而提高效率element diff
对于同一层级（具有相同父节点的）节点的新增/插入/删除/乱序等操作，传统的diff算法会按顺序一一通过component diff进行比较，对不同的节点进行删除/重建/替换操作，效率较低：
(e.g. 当上面节点顺序由ABCD改为BADC时，传统Diff算法流程：删除A，重建B，插入B，删除B，重建A，插入A，删除C，重建D，插入D，删除D，重建C，插入C共12步，即每个节点都需要删除再重建，尤其重建的效率非常低)
实际上针对上述情况，只需要进行两部移动（将A移动到B后面，将D移动到C后面）即可完成，这也是react element diff算法给出的操作结果：
每个同级节点具有独特的key
遍历每个新Virtual DOM的节点（索引记为i），如果旧Virtual DOM树同一层级具有相同的节点（需要结合key和component diff判断是否相同），且该节点当前所在索引 i 在其旧索引位置的前面，则将该节点从真实DOM树上往后移动
（即仅对存在的节点向后移动，而不对节点向前移动）
（e.g. 上面A节点在新树的索引为1，旧树的索引为0，则将A在DOM树上往后移）
对于不存在于旧DOM的新节点则直接插入到DOM树中，对于不存在于新DOM的旧节点则直接删除
Example:
(ABCD节点均在旧DOM树中，b节点新旧索引（0<1）不动，a节点（1>0）往后移动，依次类推)
(B节点不动，E节点新增，C节点不冬，A节点后移，D节点删除)
（ABC节点均后移，D节点不动。由于Diff算法只对节点进行后移，因此尽量减少类似将最后一个节点移动到列表首部的操作）
